package leetcode;

import org.junit.Assert;
import org.junit.Test;

public class ZigZagConversion {
	
	public String convert(String text, int nRows){
		if (text== null || text.length() == 0 || nRows <= 0)
			throw new IllegalArgumentException();

		if (nRows == 1)
			return text;

		int[] xs = new int[text.length()];
		int[] ys = new int[text.length()];
		
		int dir = 0;
		xs[0] = 0;
		ys[0] = 0;

		for (int p=1; p<text.length(); ++p){
			if (dir == 0){
				xs[p] = xs[p-1];
				ys[p] = ys[p-1]+1;
			} else if (dir == 1){
				xs[p] = xs[p-1]+1;
				ys[p] = ys[p-1]-1;
			}	

			if (ys[p] == 0)
				dir = 0;
			else if (ys[p] == nRows-1)
				dir = 1;
		}

		return display(text, xs, ys, nRows);
	}

	public String display(String text, int[] xs, int[] ys, int nRows){
		int mx = xs[xs.length-1]+1;
		char[] ca = new char[mx*nRows];

		for (int p=0; p< text.length(); ++p){
			int idx = ys[p] * mx  + xs[p];
			ca[idx] = text.charAt(p);
		}

		StringBuilder builder = new StringBuilder();
		for (int p=0; p< ca.length; ++p){
			if (ca[p] != '\u0000'){
				builder.append(ca[p]);
			}
		}

		return builder.toString();
	}
	
	
	/**
	 * rows = 3:
		 P   A   H   N    0, 4, 8..
		 A P L S I I G    1, 3, 5..
		 Y   I   R        2, 6, 10..
		rows = 4:
		 P     I     N    0, 6, 12..        6, 6, 6, 6...
		 A   L S   I G    1, 5, 7, 11, 13   4, 2, 4, 2
		 Y A   H R        2, 4, 8, 10, 14   2, 4, 2 ,4
		 P     I          3, 9, 15          6
		
		 rows = 5:
		 P       H       0, 8, 16..         8, 8
		 A     S I       1, 7, 9..          6, 2
		 Y   I   R       2, 6, 10..         4, 4
		 P L     I G     3, 5, 11..         2, 6
		 A       N       4, 12..            8, 8
	 * 
	 * @param text
	 * @param nRows
	 * @return
	 */
	public String convert2(String text, int nRows){
		if (nRows <=1)
			return text;
		
		StringBuilder builder = new StringBuilder();
		for (int i=0; i< nRows; ++i){
			boolean even = true;
			for (int k=i; k<text.length();){
				builder.append(text.charAt(k));
				if (i==0 || i == nRows -1){
					k += (nRows -1) * 2;
				} else {
					if (even)
						k += (nRows-1-i)*2;
					else
						k += 2*i;
					even = !even;
				}
			}
		}
		
		return builder.toString();
	}
	
	@Test
	public void testConvert(){
		ZigZagConversion conversion = new ZigZagConversion();
		
		Assert.assertEquals("PAHNAPLSIIGYIR", conversion.convert2("PAYPALISHIRING", 3));
	}
}
